//给定一个二叉树的
// root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。 
//
// 两个节点之间的路径长度 由它们之间的边数表示。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入：root = [5,4,5,1,1,5]
//输出：2
// 
//
// 示例 2: 
//
// 
//
// 
//输入：root = [1,4,5,4,4,5]
//输出：2
// 
//
// 
//
// 提示: 
//
// 
// 树的节点数的范围是
// [0, 10⁴] 
// -1000 <= Node.val <= 1000 
// 树的深度将不超过 1000 
// 
//
// Related Topics 树 深度优先搜索 二叉树 👍 818 👎 0

package leetcode.editor.cn;
//java:最长同值路径
public class Q0687LongestUnivaluePath {
    public static void main(String[] args){
        Solution solution = new Q0687LongestUnivaluePath().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
//    int res;
//    public int longestUnivaluePath(TreeNode root) {
//        if (root == null) {
//            return 0;
//        }
//        traversal(root, 0, 0);
//        return res;
//    }
//
//    // 错误，永远在局部，没有返回上一层的值，自上而下，将本层的结果传递到下一层中
//    public void traversal(TreeNode root, int left, int right) {
//        if (root == null) {
//            return;
//        }
//
//        if (root.left != null) {
//            if (root.left.val == root.val) {
//                traversal(root.left, left + 1, right);
//            } else {
//                traversal(root.left, 0, right);
//            }
//        }
//
//        if (root.right != null) {
//            if (root.right.val == root.val) {
//                traversal(root.right, left, right + 1);
//            } else {
//                traversal(root.right, left, 0);
//            }
//        }
//        res = Math.max(res, left + right);
//    }

    int res;

    public int longestUnivaluePath(TreeNode root) {
        res = 0;
        dfs(root);
        return res;
    }

    // 遍历，计算使用这个节点的最大值，要么走左边，要么走右边，取左右子树的最大值
    public int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 取当前节点左右子节点的最大路径
        int left = dfs(root.left);
        int right = dfs(root.right);
        // 使用当前节点的最大路径
        int curLeft = 0, curRight = 0;
        // 如果当前节点满足要求，则更新值
        if (root.left != null && root.left.val == root.val) {
            curLeft = left + 1;
        }

        if (root.right != null && root.right.val == root.val) {
            curRight = right + 1;
        }
        // 更新结果，当前节点的最大值
        res = Math.max(res, curLeft + curRight);
        // 经过当前节点后，只能选择走左或者右，使用大的
        return Math.max(curLeft, curRight);
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}